package com.shm.leetcode.concurrent;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author: shm
 * @dateTime: 2020/11/29 10:38
 * @description: 976.三角形的最大周长
 * 给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
 *
 * 如果不能形成任何面积不为零的三角形，返回 0。
 * 示例 1：
 *
 * 输入：[2,1,2]
 * 输出：5
 * 示例 2：
 *
 * 输入：[1,2,1]
 * 输出：0
 * 示例 3：
 *
 * 输入：[3,2,3,4]
 * 输出：10
 * 示例 4：
 *
 * 输入：[3,6,2,3]
 * 输出：8
 *  
 *
 * 提示：
 *
 * 3 <= A.length <= 10000
 * 1 <= A[i] <= 10^6
 */
public class LargestPerimeter {
    /**
     * 方法一：贪心 + 排序
     * 不失一般性，我们假设三角形的边长满足 a \leq b \leq ca≤b≤c，那么这三条边组成面积不为零的三角形的充分必要条件为 a+b>ca+b>c。
     *
     * 基于此，我们可以选择枚举三角形的最长边 cc，而从贪心的角度考虑，我们一定是选「小于 cc 的最大的两个数」作为边长 aa 和 bb，此时最有可能满足 a+b>ca+b>c，使得三条边能够组成一个三角形，且此时的三角形的周长是最大的。
     *
     * 因此，我们先对整个数组排序，倒序枚举第 ii 个数作为最长边，那么我们只要看其前两个数 A[i-2]A[i−2] 和 A[i-1]A[i−1]，判断 A[i-2]+A[i-1]A[i−2]+A[i−1] 是否大于 A[i]A[i] 即可，如果能组成三角形我们就找到了最大周长的三角形，返回答案 A[i-2]+A[i-1]+A[i]A[i−2]+A[i−1]+A[i] 即可。如果对于任何数作为最长边都不存在面积不为零的三角形，则返回答案 00。
     *
     * 复杂度分析
     * 时间复杂度：O(N \log N)O(NlogN)，其中 NN 是数组 AA 的长度。
     *
     * 空间复杂度：O(1)O(1)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/largest-perimeter-triangle/solution/san-jiao-xing-de-zui-da-zhou-chang-by-leetcode-sol/
     * @param A
     * @return
     */
    public int largestPerimeter(int[] A) {
        if (A.length<3){
            return 0;
        }
        Arrays.sort(A);
        int i=A.length-1;
        while (i>1){
//            实际两边之和大于第三边 等价于 两边之差小于第三边，判断一个就行了
//            if (A[i-2]+A[i-1]>A[i]&&A[i]-A[i-2]<A[i-1]){
            if (A[i-2]+A[i-1]>A[i]){
                return A[i]+A[i-1]+A[i-2];
            }
            i--;
        }
        return 0;
    }
}
